946. Validate Stack Sequences

Question

Given two integer arrays pushed and popped each with distinct values, return true if this could have been the result of a sequence of push and pop operations on an initially empty stack, or false otherwise.

Example 1:

Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true
Explanation: We might do the following sequence:
push(1), push(2), push(3), push(4),
pop() -> 4,
push(5),
pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

Tracking

pushed[0] => 1
stack = {1}
top != popped[0] => 4

pushed[1] => 2
stack = {1,2}
top != popped[0] => 4

pushed[2] => 3
stack = {1,2,3}
top != popped[0] => 4

pushed[3] => 4
stack = {1,2,3,4}
top == popped[0] => 4, hence pop top. stack = {1,2,3}
check the next in popped
top != popped[1] => 5

pushed[4] => 5
stack = {1,2,3,5}
top == popped[1] => 5, hence pop top. stack = {1,2,3}
top == popped[2] => 3, hence pop top. stack = {1,2}
top == popped[3] => 2, hence pop top. stack = {1}
top == popped[4] => 1, hence pop top. stack = {}

stack is empty, return true

Example 2:

Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
Output: false
Explanation: 1 cannot be popped before 2.

Constraints:

1 <= pushed.length <= 1000
0 <= pushed[i] <= 1000
All the elements of pushed are unique.
popped.length == pushed.length
popped is a permutation of pushed.

---

Approach

1. Iterate through pushed and push onto stack.
2. At the same time, check if the top of the stack is equals to elements in popped.
3. If yes, that means it is a valid stack, so we can pop the top and check the next index in popped. Stop when either there is no more items in stack or it does not match popped.
4. Continue the same for the next element in pushed.
5. After checking every element in pushed, if there is still remaining items in the stack that means this is not a valid stack sequence.

Solution

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> s;
        int j = 0;
        
        for(int i = 0; i < pushed.size(); i++){
            s.push(pushed[i]);
            
            while(!s.empty() && s.top() == popped[j]){
                s.pop();
                j++;
            }
        }
        return s.empty();
    }
};